import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Comparator;


public class AgentAStar implements Agent
{
	public AgentAStar()
	{
		
	}
	public void init(Collection<String> percepts) 
	{
		System.out.println("HELLO EVERYBODY!!! YAY!!!");
		Map map = new Map(percepts);
		Sucky sucky = new Sucky(percepts);
				
		while(map.containsDirt())
		{
			Position prevPos = sucky.getPosition();
			
			sucky = find(sucky, map, CellType.Dirty);
			
			if(sucky.getPosition().equals(prevPos))
			{
				//sucky is stuck, let's just use this path.
				break;
			}
		}
		sucky = find(sucky, map, CellType.Home);
		
		_actions = sucky.getInstructions();
		for(String s : _actions)
			System.out.println(s);
	}
	private Sucky find(Sucky sucky, Map map, CellType cellTarget)
	{
		LinkedList<Tuple<Integer, Sucky>> herd = new LinkedList<Tuple<Integer, Sucky>>();
		
		map.clearVisited();
		map.visit(sucky.getPosition());
		herd.add(new Tuple<Integer,Sucky>(heuristic(sucky, CellType.Dirty, map),sucky));
		
		while(herd.size() > 0)
		{
			Sucky target = herd.pollFirst().y;
			LinkedList<Direction> directions = target.getAvailableDirections(map);
			
			for(Direction dir : directions)
			{
				
				Sucky fork = target.forkTo(dir);
				Position pos = fork.getPosition();
				
				map.visit(pos);
				if(map.getAt(pos) == cellTarget)
				{
					if(cellTarget == CellType.Dirty)
					{
						sucky = fork.fork(ActionType.Suck);
						map.cleanCellAt(pos);
					}
					else sucky = fork;
					
					return sucky;
				}
				else addToSortedList(herd, fork, cellTarget, map);
			}
		}
		return sucky;
	}
	
	private int heuristic(Sucky state, CellType goal, Map map)
	{
		int cost = state.getCost();
		Position pos = state.getPosition();
		if(goal == CellType.Home)
		{
			Position goalPos = map.getHomeCell();
			return cost + pos.getManhattanDistanceTo(goalPos);
		}
		else if(goal == CellType.Dirty)
		{
			Comparator<Position> comp = new Comparator<Position>()
			{
			    @Override
			    public int compare(Position o1, Position o2)
			    {
			    	Position pivot = AgentAStar.myPosition;
			    	Map map = AgentAStar.myMap;
			    	int len1 = pivot.getManhattanDistanceTo(o1);
			    	int len2 = pivot.getManhattanDistanceTo(o2);
			    	Position testPos = new Position(0,0);
			    	
			    	double step = 1.0 / (Math.min(numWallTests, Math.min(len1, len2) - 1) + 1);
			    	for(double i = step; i < 1; i += step)
			    	{
			    		CellType c = map.getAt(testPos.setLerp(pivot, o1, i));
			    		if(c == CellType.Wall)
			    		{
			    			len1 += costForWallHit;
			    			break;
			    		}
			    	}
			    	for(double i = step; i < 1; i += step)
			    	{
			    		CellType c = map.getAt(testPos.setLerp(pivot, o2, i));
			    		if(c == CellType.Wall)
			    		{
			    			len2 += costForWallHit;
			    			break;
			    		}
			    	}
			    	
			    	return len1 - len2;
			    }
			};
			
			myPosition = pos;
			myMap = map;
			
			LinkedList<Position> dirtyCells = map.getDirtyCells();
			Collections.sort(dirtyCells,comp);
			
			if(dirtyCells.size() > 0)
			{
				Position goalPos = dirtyCells.getFirst();
				int length = pos.getManhattanDistanceTo(goalPos);
		    	Position testPos = new Position(0,0);
		    	
		    	double step = 1.0 / (Math.min(numWallTests, length - 1) + 1);
		    	for(double i = step; i < 1; i += step)
		    	{
		    		CellType c = map.getAt(testPos.setLerp(pos, goalPos, i));
		    		if(c == CellType.Wall)
		    		{
		    			length += costForWallHit;
		    			break;
		    		}
		    	}
		    	cost += length;
			}
			
			return cost;
			
			/*
			// heuristic version 1
			//searching for absolute nearest dirty cell
			Position testPos = new Position(0,0);
			int maxRange = Math.max(map.getWidth(), map.getHeight());
			for(int range = 1; range < maxRange; range++)
			{
				for(int i = -range; i < range; i++)
				{
					testPos.x = pos.x + i;
					testPos.y = pos.y - range;
					CellType cell = map.getAt(testPos);
					if(cell == CellType.Dirty) return cost + pos.getManhattanDistanceTo(testPos);
					
					testPos.y = pos.y + range;
					cell = map.getAt(testPos);
					if(cell == CellType.Dirty) return cost + pos.getManhattanDistanceTo(testPos);
				}
				range--;
				for(int i = -range; i < range; i++)
				{
					testPos.x = pos.x - range;
					testPos.y = pos.y + i;
					CellType cell = map.getAt(testPos);
					if(cell == CellType.Dirty) return cost + pos.getManhattanDistanceTo(testPos);
					
					testPos.x = pos.x + range;
					cell = map.getAt(testPos);
					if(cell == CellType.Dirty) return cost + pos.getManhattanDistanceTo(testPos);
				}
				range++;
			}*/
		}
		//if all else fails
		return cost;
	}
	
	private void addToSortedList(LinkedList<Tuple<Integer,Sucky>> list, Sucky sucky, CellType goal, Map map)
	{
		int cost = heuristic(sucky, goal, map);
		int index = 0;
		Iterator<Tuple<Integer, Sucky>> iterator = list.iterator();
		while(iterator.hasNext())
		{
			Tuple<Integer,Sucky> tuple = iterator.next();
			int targetCost = tuple.x;
			if(targetCost >= cost)
			{
				break;
			}
			index++;
		}
		list.add(index, new Tuple<Integer,Sucky>(cost, sucky));
	}
	
	private LinkedList<String> _actions;
	private Boolean _givingUp = false;

	public String nextAction(Collection<String> percepts)
	{
		if(_actions != null)
			return _actions.poll();
		else
		{
			Boolean temp = _givingUp;
			_givingUp = true;
			if(temp) return "TURN_OFF";
			else return "TURN_ON";
		}
	}
	
	private static Position myPosition;
	private static Map myMap;
	private static int numWallTests = 4;
	private static int costForWallHit = 2;
}
